#将有序数组转换为二叉搜索树
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def build (left, right):
            if left >= right:
                return None
            mid = left +((right-left)>>1)
            return TreeNode(nums[mid], build(left, mid), build(mid+1, right))
        return build(0, len(nums))


#搜索插入位置
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target < nums[0]:
            return 0
        if target > nums[-1]:
            return len(nums)
        a = nums[0]
        b = nums[-1]
        while nums.index(b)-nums.index(a) > 1:
            c = (nums.index(a)+nums.index(b))/2
            c = int(c)
            if nums[c] > target:
                b = nums[c]
            if nums[c] < target:
                a = nums[c]
            if nums[c] == target:
                return c
        if a == target:
            return nums.index(a)
        if b == target:
            return nums.index(b)
        if a < target and b > target:
            return nums.index(b)


#二进制求和
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        while len(a) > len(b):
            b = '0'+b
        while len(a) < len(b):
            a = '0'+a
        tmp = 0
        a, b = list(a), list(b)
        for i in range(len(a)-1, -1, -1):
            cur = int(a[i]) + int(b[i]) + tmp
            if cur == 3:
                b[i] = '1'
                tmp = 1
            if cur == 2:
                b[i] = '0'
                tmp = 1
            if cur ==1:
                b[i] = '1'
                tmp = 0
            if cur == 0:
                b[i] = '0'
                tmp = 0
        if tmp == 1:
            b = ['1']+b
        return ''.join(b)


#颠倒二进制位
class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for i in range(32):
            res = (res << 1) | (n & 1)
            n >>= 1
        return res



#位1的个数
class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += n & 1
            n >>=1
        return res


#只出现一次的数字
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        x = 0
        for i in range(len(nums)):
            x ^=nums[i]
        return x


#回文数
class Solution:
    def isPalindrome(self, x: int) -> bool:
        c = str(x)
        d = list(c)
        b = d.copy()
        b.reverse()
        if d == b:
            return True
        else:
            return False


#加一
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        s = ''
        q = []
        for i in digits:
            s = s + str(i)
        s = int(s)
        s += 1
        for j in str(s):
            q.append(int(j))
        return q


#x的平方根
class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0 or x == 1:
            return x
        l, h, res = 1, x, -1
        while l <= h:
            mid = (l + h)//2
            if mid*mid <= x:
                l = mid+1
                res = mid
            else:
                h = mid - 1
        return res


#爬楼梯
class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1
        for i in range(n-1):
            a, b = b, a+b
        return b